//题目:
// 在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
// 你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。
// 最终，我们到过网格的所有 rows x cols 个空间。
// 按照访问顺序返回表示网格位置的坐标列表。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) 
    {
        int sum_count=rows*cols,steps=0;

        vector<vector<int>> ret;
        pair<int,int> pos(rStart,cStart);

        //定义方向矢量和方向集
        int index=-1;
        pair<int,int> dir(0,1);
        pair<int,int> directions[4]={{0,1},{1,0},{0,-1},{-1,0}};

        ret.push_back({rStart,cStart});
        while(ret.size()<sum_count)
        {
            //向着dir方向走steps步
            for(int i=0;i<steps;i++)
            {
                pos.first+=dir.first,pos.second+=dir.second;
                if(pos.first>=0 && pos.first<rows && pos.second>=0 && pos.second<cols)
                    ret.push_back({pos.first,pos.second});
            }
            //更新dir和steps
            (index++);
            index%=4;
            dir=directions[index];

            if(index==0 || index==2) steps++;

            //steps: 1、1、2、2、3、3、4、4、5
        }
        return ret;
    }
};